package com.yangli.leecode.mashib.interview;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @Description
 * @Author liyang
 * @Date 2023/2/8 11:39
 */
public class Sixteen {
    public static void main(String[] args){
        Sixteen sixteen = new Sixteen();

        System.out.println(sixteen.removeInvalidParentheses("((()"));
        System.out.println(sixteen.removeInvalidParentheses("x("));

    }

    public List<String> removeInvalidParentheses(String s){
        Set<String> res = new HashSet<>();
        function(s, res, 0, 0, new char[]{'(', ')'});
        System.out.println(res);

        return new ArrayList<>(res);
    }

    public void function(String s, Set<String> ans, int checkIndex, int deleteIndex, char[] pro){
        int count = 0;
        for (int i = checkIndex; i < s.length(); i++) {
            if (s.charAt(i) == pro[0]) {
                count++;
            }
            if (s.charAt(i) == pro[1]) {
                count--;
            }
            if (count < 0) {
                for (int j = deleteIndex; j <= i; ++j) {
                    if (s.charAt(j) == pro[1] && (j == checkIndex || s.charAt(j - 1) != pro[1])) {  //j == checkIndex
                        function(s.substring(0, j) + s.substring(j + 1, s.length()), ans, i, j, pro);
                    }
                }
                return;

            }
        }

        String reverse = new StringBuilder(s).reverse().toString();
        if (pro[0] == '(') {
            function(reverse, ans, 0, 0, new char[]{')', '('});
        } else {
            ans.add(reverse);
        }

    }
}
